#include <vector>
#include <string>
#include <queue>

using namespace std;

// 分层图最短路，又叫扩点最短路

// 不把实际位置看做图上的点，而是把 实际位置及其状态的组合 看做是图上的点，然后搜索
// bfs 或者 Dijkstra 的过程不变，只是扩了点（分层）而已
// 原理简单，核心在于如何扩点、如何到达、如何算距离，每个题可能都不一样


// 获取所有钥匙的最短路径
// 给定一个二维网格 grid ，其中：
// '.' 代表一个空房间、'#' 代表一堵、'@' 是起点
// 小写字母代表钥匙、大写字母代表锁
// 从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间
// 不能在网格外面行走，也无法穿过一堵墙
// 如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
// 假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，
// 字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母
// 换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁
// 另外，代表钥匙和锁的字母互为大小写并按字母顺序排列
// 返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
// 测试链接：https://leetcode.cn/problems/shortest-path-to-get-all-keys

// 本题状态的个数 30 * 30 * 2 ^ 6
class Solution 
{
private:
    const int MAXN = 31;
    const int MAXM = 31;
    const int MAXK = 6;

public:
    int shortestPathAllKeys(vector<string>& grid) 
    {
        // 0：上，1：右，2：下，3：左
        int move[5] = {-1, 0, 1, 0, -1};
        int m = grid.size(), n = grid[0].size();
        bool visited[MAXN][MAXM][1 << MAXK];
        memset(visited, 0, sizeof(visited));

        // first：pos，second：收集钥匙的状态
        // 其中 pos = x * n + y，则 x = pos / n，y = pos % n 
        // x * n + y 是表示点常用的技巧，将点（x, y）进行压缩
        // 注：使用 tuple 也是可以的，queue<tuple<int, int, int>> q
        queue<pair<int, int>> q;
        int key = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j] == '@')
                {
                    // 0：000000
                    q.push({i * n + j, 0});
                }
                // key 是钥匙的全集
                if(grid[i][j] >= 'a' && grid[i][j] <= 'f')
                {
                    key |= 1 << (grid[i][j] - 'a');
                }
            }
        }

        int level = 1;
        while(!q.empty())
        {
            // 一层一层地遍历
            int size = q.size();
            while(size--)
            {
                auto [pos, s] = q.front();
                q.pop();
                int x = pos / n, y = pos % n;
                for(int i = 0; i < 4; ++i)
                {
                    int nx = x + move[i], ny = y + move[i + 1], ns = s;
                    if(nx < 0 || nx == m || ny < 0 || ny == n || grid[nx][ny] == '#') 
                    {
                        // 越界或者障碍
                        continue;
                    }
                    if(grid[nx][ny] >= 'A' && grid[nx][ny] <= 'F' && ((ns & (1 << (grid[nx][ny] - 'A'))) == 0))
                    {
						// 是锁，又没有对应的钥匙
                        continue;
                    }
                    if(grid[nx][ny] >= 'a' && grid[nx][ny] <= 'f')
                    {
                        // 是某把钥匙
                        ns |= 1 << (grid[nx][ny] - 'a');
                    }

                    // 常见剪枝
                    // 发现终点直接返回
                    // 不用等都结束
                    if(ns == key) return level;
                    if(!visited[nx][ny][ns])
                    {
                        visited[nx][ny][ns] = true;
                        q.push({nx * n + ny, ns});
                    }
                }
            }
            ++level;
        }

        return -1;
    }
};